Access Control Lists (ACLs) are a commonly used approach to filtering IP traffic. ACLs comprise lists of rules referred to as Access Control Entries (ACEs). In an example case, the ACEs map inbound packets to outbound ports as a function of source and destination addresses, and indicate whether given inbound packets should be permitted (routed) or denied (discarded). Of course, ACLs can be used for other purposes, including Network Address Translation (NAT) processing, policy-based routing, etc.
With the increasing “intelligence” of IP networks, such as those implemented in the latest telecommunication networks, there is an increasing need for more sophisticated packet classification, security filtering, policy routing, packet redirecting for service chain processing, OpenFlow processing switches, etc. “OpenFlow” is an open interface that provides remote control of the forwarding tables in network routers, switches, and access points, and thus allows dynamic control of network behavior, policies, etc.
As might be imagined, the number of ACEs needed in an ACL can be quite large. It is not uncommon for an ACL to include more than a thousand ACEs, e.g., up to four thousand or more ACEs. Moreover, there may be different ACLs for different activities and for different protocol families, e.g., each ACL “bind point” in the data plane corresponds to a different protocol family type, like IPv4, IPv6, Virtual LANs (VLANs), Multi-Protocol Label Switching (MPLS), etc. The total number of rules across all ACLs implemented in a network switch or router can be quite large, e.g., well over a hundred thousand.
ACL-based search types include Longest Prefix Match (LPM), such as are used for Source IP-IPv4/IPv6, Destination IP-IPv4/IPv6), exact match searching, which is used for protocols or flags, and range matching, which is used for TCP/UDP source port and destination port. In this regard, the Ternary CAM (TCAM) is a specialized type of Content Addressable Memory (CAM) that is designed for rapid table lookups, based on packets passing through a switch or router. However, there generally are significant power, cost, and space constraints governing the amount of TCAM available for fast searching of large ACLs and/or large numbers of ACLs.
Other approaches include algorithmic solutions such as Modified Recursive Flow Classification (MRFC). Characteristically, however, MRFC-based solutions require many external memory accesses, because the large amount of memory needed in MRFC processing typically does not fit into the on-chip memories of digital processors used as routing engines. Another issue is that MRFC does not appear to work as well with wider packet “keys,” which are becoming more prevalent as IPv6 usage increases.